package 剑指offer;

public class _42连续子数组的最大和 {
	 //使用到动态规划
	 //dp[i] = dp[i-1] + nums[i] dp[i-1] > 0
	//dp[i] = nums[i] dp[i-1] <= 0
	  public int maxSubArray(int[] nums) {
		int []dp = new int[nums.length];
		dp[0] = nums[0];
		for (int i = 1; i < nums.length; i++) {
			if(dp[i-1]>0) {
				dp[i] = dp[i-1]+nums[i];
			}else {
				dp[i] = nums[i];
			}
		}
		int max =dp[0];
		for (int i = 0; i < dp.length; i++) {
			if (max<dp[i]) {
				max = dp[i];
			}
		}
		  
		  return max;		  
	    }

}
